#include <iostream>
#include <vector>
#include <sys/time.h>
#include <unistd.h>
#include <arm_neon.h>
#include "mpi.h"
#define N 4800
using namespace std;
int n=100;
float m[N][N],init_m[N][N];



void init(int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            init_m[i][j]=0;
        init_m[i][i]=1.0;
        for(int j=i+1;j<n;j++)
            init_m[i][j]=rand()%1000+1;
    }
    for(int k=0;k<n;k++)
        for(int i=k+1;i<n;i++)
            for(int j=0;j<n;j++)
                init_m[i][j]=int((init_m[i][j]+init_m[k][j]))%1000+1.0;
}
void reset(int n){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            m[i][j]=init_m[i][j];
}

void serial(int n){ //串行
    struct timeval h, t;
    float time = 0.0;
    gettimeofday(&h, NULL);
      for(int k=0;k<n;k++){
          for(int j=k+1;j<n;j++)
              m[k][j]/=m[k][k];
          m[k][k]=1.0;
          for(int i=k+1;i<n;i++){
              for(int j=k+1;j<n;j++)
                  m[i][j]-=m[i][k]*m[k][j];
              m[i][k]=0;
          }
      }
    gettimeofday(&t, NULL);
    time += 1000*(t.tv_sec - h.tv_sec) + 0.001*(t.tv_usec - h.tv_usec);
    cout<<"serial: "<<time<<" ms"<<endl;
    return;
}

int comm_sz;
int my_rank;

MPI_Init(NULL, NULL);
MPI_Comm_size(MPI_COMM_WORLD, &comm_sz);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);

int range = ELI / comm_sz;
int r1, r2;
r1 = my_rank * range;
if (my_rank != comm_sz - 1)
    r2 = r1 + range - 1;
else
    r2 = ELI - 1;

for (int i = N - 1; i >= 0; i -= p)
{
    if (i - p < 0)
        p = i + 1;
    for (int j = r1; j <= r2; j++)
    {
        if (eline[j].b == 0)
        {
            for (int k = 0; k < p; k++)
            {
                if (eline[j].bit[i - k] == 1)
                    eline[j].bit ^= eliminer[i - k];
                if (eline[j].bit.none())
                {
                    eline[j].b = true;
                    break;
                }
                else
                {
                    for (int l = eline[j].num; l >= 0; l--)
                    {
                        if (eline[j].bit[l] == 1)
                        {
                            eline[j].num = l;
                            break;
                        }
                    }
                    if (eliminer[eline[j].num].none())
                    {
                        eline[j].b = true;
                        break;
                    }
                }
            }
        }
    }
}
if (my_rank != 0)
    MPI_Send(&eline[r1], (r2 - r1 + 1) * sizeof(line), MPI_BYTE, 0, 1, MPI_COMM_WORLD);
else
    for (int q = 1; q < comm_sz; q++)
    {
        if (q != comm_sz - 1)
            MPI_Recv(&eline[q * range], range * sizeof(line), MPI_BYTE, q, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        else
            MPI_Recv(&eline[q * range], sizeof(line) * (range + ELI % comm_sz), MPI_BYTE, q, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
    }
if (my_rank == 0)
{
    for (int j = r1; j < ELI; j++)
    {
        if (eline[j].b == 1)
        {
            if (eliminer[eline[j].num].none())
                eliminer[eline[j].num] ^= eline[j].bit;
            else
            {
                eline[j].b = 0;
                for (int k = 0; k < p; k++)
                {
                    if (eline[j].bit[i - k] == 1)
                        eline[j].bit ^= eliminer[i - k];
                }
                if (eline[j].bit.none())
                {
                    eline[j].b = true;
                    break;
                }
                else
                {
                    for (int l = eline[j].num; l >= 0; l--)
                    {
                        if (eline[j].bit[l] == 1)
                        {
                            eline[j].num = l;
                            break;
                        }
                    }
                    if (eliminer[eline[j].num].none())
                    {
                        eliminer[eline[j].num] ^= eline[j].bit;
                        eline[j].b = true;
                        break;
                    }
                }
            }
        }
    }
}